//
//  BKTreeNode.h
//  swp
//
//  Created by Rune Juul Laugesen on 03/12/13.
//
//

#ifndef Dictionary_BKTreeNode_h
#define Dictionary_BKTreeNode_h

#include <string>
#include <vector>
#include <map>

using namespace std;

static int LevenshteinDistance(string s, string t)
{
    int ret = 0;
    
    if (s == "" || t == "")
    {
        throw "Strings must be different from null";
    }
    
    int n = (int)s.length();
    int m = (int)t.length();
    
    if (n == 0)
    {
        return m;
    } else if (m == 0)
    {
        return n;
    }
    
    int* p = new int[n + 1];
    int* d = new int[n + 1];
    int* swap;
    
    int cost; // cost
    
    for (int i = 0; i <= n; i++)
    {
        p[i] = i;
    }
    
    for (int j = 1; j <= m; j++)
    {
        char tj = t[j - 1];
        d[0] = j;
        
        for (int i = 1; i <= n; i++)
        {
            cost = s[i - 1] == tj ? 0 : 1;
            d[i] = min(min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
        }
        
        swap = p;
        p = d;
        d = swap;
    }
    
    ret = p[n];
    p = NULL;
    d = NULL;
    
    return ret;
}

class BKTreeNode
{
private:
    string _name;
    map<int, BKTreeNode> _children;
    
public:
    BKTreeNode() : _name(""){};
    BKTreeNode(string name);
    BKTreeNode* childAtDistance(int pos);
    map<int, string> Search(string word, int maxdistance);
    void addChild(int pos, BKTreeNode* child);
    string GetName();
};


#endif
